#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

#define TYPE int

typedef struct Node
{
	TYPE data;
	struct Node* left;
	struct Node* right;
}Node;



//创建结点
Node* creat_node(TYPE data)
{
	Node* node = malloc(sizeof(Node));
	node->data=data;
	node->left=NULL;
	node->right=NULL;
	return node;
}

//中序
void in_show(Node* root);
void post_show(Node* root)
{
	if(NULL == root) return;
	post_show(root->left);
	post_show(root->right);
	printf("%d  ",root->data);
}
void _add_tree(Node** root,Node* node);
void add_tree(Node** root,TYPE data);
bool del_tree(Node** root,TYPE data);


//====================根据前序中序建立二叉树==========================

Node* re_tree(TYPE* prev,TYPE* in,size_t size)
{
	if(size <=0) return NULL;
	Node* root = creat_node(prev[0]);
	int i = 0;
	for(;i<size;i++)
	{
		if(prev[0]==in[i])
		break;
	}
	root->left=re_tree(prev+1,in,i);
	root->right=re_tree(prev+i+1,in+i+1,size-i-1);
	return root;
}

//=================================================================

int main()
{
	Node* tree =NULL;// creat_node(50);
	for(int i=0;i<10;i++)
	{
		TYPE data=rand()%100;
		add_tree(&tree,data);
		printf("%d\n",data);
	}
	printf("------------------------------\n");
	printf("\n中序：");
	in_show(tree);
	printf("\n");
	TYPE prev[]={1,2,4,7,3,5,6,8};
	TYPE in[]={4,7,2,1,5,3,8,6};
	Node* tree3 =re_tree(prev,in,8);
	in_show(tree3);



}


//中序
void in_show(Node* root)
{
	if(NULL == root) return;
	in_show(root->left);
	printf("%d ",root->data);
	in_show(root->right);
}




//修改后的添加===================
void _add_tree(Node** root,Node* node)
{
	if(NULL == *root) *root = node;

	else if((*root)->data > node->data)
		_add_tree(&(*root)->left,node);
	else
		_add_tree(&(*root)->right,node);
}

void add_tree(Node** root,TYPE data)
{
	_add_tree(root,creat_node(data));
}

//===============================

//删除
bool del_tree(Node** root,TYPE data)
{
	if((*root)->data ==data)
	{
		Node* node =* root;
		*root = node->left;
		_add_tree(root,node->right);
		free(node);			
		return true;	
	}
	else if((*root)->data >data)
		return del_tree(&(*root)->left,data);
	else 
		return del_tree(&(*root)->right,data);
}


